#include "List.cpp"

// 有问题
ListNode* partition(ListNode* head, int x){
    ListNode* newList = (ListNode*) malloc(sizeof(ListNode));
    newList->next = NULL;
    ListNode* pos = newList;
    ListNode* p = head;
    ListNode* pre = newList;
    while(p != NULL) {
        if (p->data < x) {
            ListNode* q = p->next;
            pre->next = p->next;
            p->next = pos->next;
            pos->next = p;
            pos = pos->next;
            p = q;
            if (pre->next != p) {
                pre = pos->next;
            }
            continue;
        }
        pre = p;
        p = p->next;
    }
    return newList->next;
}

ListNode* partition2(ListNode* head, int x){
    ListNode* lowPos = (ListNode*) malloc(sizeof(ListNode));
    lowPos->next = NULL;
    ListNode* newList = lowPos;
    ListNode* upPos = (ListNode*) malloc(sizeof(ListNode));
    ListNode* up = upPos;
    up->next = NULL;
    ListNode* p = head;
    while(p != NULL) {
        ListNode* q= p->next;
        if (p->data < x) {
           lowPos->next = p;
           p->next = NULL;
           lowPos = lowPos->next;
        } else{
            upPos->next = p;
            p->next = NULL;
            upPos = upPos->next;
        }
        p = q;
    }
    lowPos->next = up->next;
    return newList->next;
}

int main() {
    int arr[] = {1,2,3,2,4,5,2};
    List list = CreateListByArray(arr,ARRAY_SIZE(arr));
    List newList =  partition2(list,3);
    PrintList(newList);
}
